package com.zhang.study.chapter03;

import com.zhang.study.chapter03.node.Node;

import java.util.ArrayList;
import java.util.List;

import static com.zhang.util.NodeUtil.generateRandomLinkedList;

/**
 * 删除链表中给定的值
 */
public class Code03_RemoveNode {

    /**
     * 删除链表中给定的值
     *
     * @param head 给定的头节点
     * @param num  删除的值
     * @return 删除完成后的头节点
     */
    public static Node removeNode(Node head, int num) {
        while (head != null) {
            if (head.value != num) {
                break;
            }
            head = head.next;
        }
        Node cur = head;
        Node pre = head;
        while (cur != null) {
            if (cur.value == num) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

    public static List<Node> testRemoveNode(Node head, int num) {
        List<Node> nodes = new ArrayList<>();
        if (head == null) {
            return nodes;
        }
        while (head != null) {
            if (head.value != num) {
                nodes.add(head);
            }
            head = head.next;
        }
        return nodes;
    }

    public static boolean checkRemoveList(List<Node> list, Node head) {
        boolean flag = true;
        if ((list == null || list.isEmpty()) && head == null) {
            return true;
        }
        if (list == null) {
            return false;
        }
        for (Node node : list) {
            if (node.value != head.value) {
                flag = false;
            }
            head = head.next;
        }
        return flag;
    }

    public static void main(String[] args) {
        int len = 500000;
        int value = 1000;
        int testTime = 100;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            // 生成链表头结点
            Node node1 = generateRandomLinkedList(len, value);
            int num = ((int) (Math.random() * value ));
            node1 = removeNode(node1, num);
            List<Node> nodes = testRemoveNode(node1, num);
            if (!checkRemoveList(nodes, node1)) {
                System.out.println("Oops!");
            }

        }
        System.out.println("test finish!");
    }


}
